/**
 * reference: http://sujitpal.blogspot.com/2006/05/java-data-structure-generic-tree.html
 * Represents a Tree of Objects of generic type T. The Tree is represented as
 * a single rootElement which points to a List<Node<T>> of children. There is
 * no restriction on the number of children that a particular node may have.
 * This Tree provides a method to serialize the Tree into a List by doing a
 * pre-order traversal. It has several methods to allow easy updation of Nodes
 * in the Tree.
 */
package edu.cmu.km.core;

import java.util.*;

/**
 * @author Lucas Xu
 *
 */


/**
 * Represents a Tree of Objects of generic type T. The Tree is represented as
 * a single rootElement which points to a List<Node<T>> of children. There is
 * no restriction on the number of children that a particular node may have.
 * This Tree provides a method to serialize the Tree into a List by doing a
 * pre-order traversal. It has several methods to allow easy updation of Nodes
 * in the Tree.
 */
public class Tree<T> {
 
    private Node<T> rootElement;
     
    /**
     * Default constructor.
     */
    public Tree() {
        super();
    }
 
    /**
     * Return the root Node of the tree.
     * @return the root element.
     */
    public Node<T> getRootElement() {
        return this.rootElement;
    }
 
    /**
     * Set the root Element for the tree.
     * @param rootElement the root element to set.
     */
    public void setRootElement(Node<T> rootElement) {
        this.rootElement = rootElement;
    }
     
    /**
     * Returns the Tree<T> as a List of Node<T> objects. The elements of the
     * List are generated from a pre-order traversal of the tree.
     * @return a List<Node<T>>.
     */
    public List<Node<T>> toList() {
    	return this.preTraverse();
    }
     
    /**
     * Returns a String representation of the Tree. The elements are generated
     * from a pre-order traversal of the Tree.
     * @return the String representation of the Tree.
     */
    public String toString() {
        return toList().toString();
    }
     
    
    /**
     * Returns the Tree<T> as a List of Node<T> objects. The elements of the
     * List are generated from a pre-order traversal of the tree.
     * @return a List<Node<T>>.
     */
    public List<Node<T>> preTraverse() {
        List<Node<T>> list = new ArrayList<Node<T>>();
        preTrav(rootElement, list);
        return list;
    }

    /**
     * Traverse the Tree in pre-order style. This is a recursive method, and is
     * called from the toList() method with the root element as the first
     * argument. It appends to the second argument, which is passed by reference     
     * as it recurses down the tree.
     * @param element the starting element.
     * @param list the output of the traverse.
     */
    private void preTrav(Node<T> element, List<Node<T>> list) {
        list.add(element);
        for (Node<T> data : element.getChildren()) {
        	preTrav(data, list);
        }
    }
    
    /**
     * Returns the Tree<T> as a List of Node<T> objects. The elements of the
     * List are generated from a post-order traversal of the tree.
     * @return a List<Node<T>>.
     */
    public List<Node<T>> postTraverse() {
        List<Node<T>> list = new ArrayList<Node<T>>();
        posTrav(rootElement, list);
        return list;
    }

    /**
     * Traverse the Tree in post-order style. This is a recursive method, and is
     * called from the toList() method with the root element as the first
     * argument. It appends to the second argument, which is passed by reference     
     * as it recurses down the tree.     
     * @param element
     * @param list
     */
	private void posTrav(Node<T> element, List<Node<T>> list){
        for (Node<T> data : element.getChildren()) {
        	posTrav(data, list);
        }
        list.add(element);    	
    }
	
	
	/**
	 * Return the number of nodes in the tree
	 * @return the number of nodes in the tree
	 */
	public int getNumberOfNodes(){
		return this.toList().size();
	}
//    
//    /**
//     * Traverse the Tree in-order style. Note that this method is only valid for binary tree. 
//     */
//    private void inTrav(){
//    	
//    }
//    
	
	

	/**
	 * convert the Tree to a Forest
	 * @return the Forest with one member tree
	 */
	public Forest<T> toForest(){
		Forest<T> forest = new Forest<T>();
		forest.addMemberTree(this);
		return forest;		
	}
    
    
	
	
	/**
	 * Call this method if you want to print out the tree in a "tree" form
	 */
	public void printTree(){
		printNode(this.rootElement, "|---", 0);		
	}
	/**
	 * print a node, and  print its children recursively.
	 * @param node
	 * @param ident
	 * @param i
	 */
	private void printNode(Node<T> node, String ident, int i){
		String s= node.getData().toString();		
		s = s.replaceAll("\n", "\\\\n");
		s = s.replaceAll("\r", "\\\\r");
		System.out.printf("%2d", i);

		System.out.println(ident+s);
        for (Node<T> child : node.getChildren()) {
        	printNode(child, "|	"+ident, i+1);
        }
		
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
    /**
     * This main function is used for testing the Node class.  
     * @param args
     */
    public static void main(String[] args){
    	Tree<String> stringTree = new Tree<String>();
    	Node<String> root=new Node<String>("root");
    	Node<String> child1=new Node<String>("c1");
    	Node<String> child2=new Node<String>("c2");
    	Node<String> child3=new Node<String>("c3");
    	Node<String> child4=new Node<String>("c4");
    	Node<String> child5=new Node<String>("c5");
    	
    	root.addChild(child1);
    	root.addChild(child2);
    	root.addChild(child3);
    	child3.addChild(child4);
    	child3.addChild(child5);
    	
    	stringTree.setRootElement(root);
    	List<Node<String>> stringlist= stringTree.toList();
    	System.out.println(stringlist);
    	
    	stringTree.printTree();
    }
    
    
}

